//给定一个整数数组
// prices，其中第 prices[i] 表示第 i 天的股票价格 。 
//
// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 
//
// 
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 
// 
//
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 
//
// 
//
// 示例 1: 
//
// 
//输入: prices = [1,2,3,0,2]
//输出: 3 
//解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 
//
// 示例 2: 
//
// 
//输入: prices = [1]
//输出: 0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= prices.length <= 5000 
// 0 <= prices[i] <= 1000 
// 
//
// Related Topics 数组 动态规划 👍 1589 👎 0


package leetcode.editor.cn;

// [309]买卖股票的最佳时机含冷冻期

public class BestTimeToBuyAndSellStockWithCooldown_309 {
    public static void main(String[] args) {
        Solution solution = new BestTimeToBuyAndSellStockWithCooldown_309().new Solution();
        solution.maxProfit(new int[]{2, 4, 3, 6, 8, 5, 2, 6, 8, 4, 3, 6, 3});
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 计算每日差价，+ 题目：打家劫舍
     */
    class Solution {
        public int maxProfit(int[] prices) {
            if (prices.length == 1) {
                return 0;
            }
            return maxProfit1(prices);
        }

        //动态规划
        public int maxProfit1(int[] prices) {
            if (prices.length == 1) {
                return 0;
            }
            //0：持有股票，1：保持卖出状态（冷冻期已过），2：卖出股票状态（卖出的那一天），3：冷冻期
            int[][] dp = new int[prices.length][4];
            dp[0][0] = -prices[0];
            for (int i = 1; i < prices.length; i++) {
                dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3]) - prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
                dp[i][2] = dp[i - 1][0] + prices[i];
                dp[i][3] = dp[i - 1][2];
            }
            int[] ans = dp[prices.length - 1];
            return Math.max(ans[1],Math.max(ans[2],ans[3]));
        }

        private int getAns(int[] arr) {
            if (arr.length == 1) {
                return Math.max(arr[0], 0);
            }
            if (arr.length == 2) {
                return Math.max(Math.max(arr[0], arr[1]), 0);
            }
            int[] dp = new int[arr.length];
            dp[0] = Math.max(0, arr[0]);
            dp[1] = Math.max(Math.max(arr[0], arr[1]), 0);
            for (int i = 2; i < dp.length; i++) {
                dp[i] = Math.max(dp[i - 2] + arr[i], dp[i - 1]);
            }
            return dp[arr.length - 1];
        }

        private int[] getResArray(int[] arr) {
            if (arr == null || arr.length == 0) {
                return null;
            }
            if (arr.length == 1) {
                return new int[0];
            }
            int[] ans = new int[arr.length - 1];
            for (int i = 0; i < ans.length; i++) {
                ans[i] = arr[i + 1] - arr[i];
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}